
package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         338,
		Discription: "O(n)解决0...n每个数的二进制表示中1的个数",
		Level:       1,
		Labels: map[string]int{
			"位运算":    1,
			"动态规划":    1,
		},
	})
}

func CountBits(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		//i&(i-1)会把i的从右往左开始第一个1变为0
		bits[i] = bits[i&(i-1)] + 1
	}

	return bits
}